package leetcode.editor.cn;
 
/**
 * 解码方法
 * @author qulq
 * @date 2024-07-13 10:29:16
 */
public class T91_DecodeWays{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new T91_DecodeWays().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numDecodings(String s) {
		// dp[i] = 数字串s【前】i个数字解密有多少种方式
		// dp[i] = dp[i-1] + dp[i-2]
		// dp[0] = 1, 即空串有1种方式解密
		char[] c = s.toCharArray();
		if (c.length == 0) {
			return 0;
		}
		int[] dp = new int[c.length + 1];
		dp[0] = 1;
		for (int i = 1; i <= c.length; i++) {
			// last digit
			int num1 = c[i - 1] - '0';
			if (num1 >= 1 && num1 <= 9) {
				dp[i] += dp[i - 1];
			}
			// last two digit
			if (i >= 2) {
				int num2 = (c[i - 2] - '0') * 10 + (c[i - 1] - '0');
				if (num2 >= 10 && num2 <= 26) {
					dp[i] += dp[i - 2];
				}
			}
		}
		return dp[c.length];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}